#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int N = 1e4 + 10;
int a[N];
void f()
{
	a[1] = 1, a[2] = 2;
	for (int i = 3;i <= 10000;i++)
	{
		a[i] = (a[i - 2] + a[i - 1]) % 10000;
	}
}
int main()
{
	f();
	int n;
	while (cin >> n)
	{
		// string res;
		while (n--)
		{
			int x;
			cin >> x;
			printf("%04d", a[x]);
		}
		cout << endl;
	}
	return 0;
}